package someTestExcemple.huaweiOd.binarySearch;

//华为OD机试 - 猴子吃桃 - 二分查找（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/137126184
import java.util.*;
/*为了解决孙悟空在规定时间内吃完所有蟠桃的最小速度问题，
        可以使用二分查找算法。因为速度 K 的取值范围是有边界的，
        最小是 1，最大是所有蟠桃树中蟠桃数量的最大值。
        (超过这个最大值的速度没有实际意义。因为即使速度再提高，也不会让吃完所有蟠桃的总时间减少,每颗蟠桃都可以在1小时内吃完。)
        在这个范围内进行二分查找，找到满足在 H 小时内吃完所有蟠桃的最小速度。*/

public class MonkeyEatPeach {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //天兵将离开时间
        int H =  arr[arr.length-1];
        //获得各树蟠桃个数
        //todo Arrays.copyOf学习一下
        arr = Arrays.copyOf(arr,arr.length-1);
        //按蟠桃数量由小到大排序
        Arrays.sort(arr);
        //二分查找 在K可以取值的1到所有蟠桃树中蟠桃数量的最大值,其中找最小值满足要求的
        int left = 1;
        int right = arr[arr.length-1];
        int result = Integer.MAX_VALUE;
        int count =0; //统计一下执行了多少次
        while(left<=right) {
            int mid = (left+right)/2;
            if(canEatAll(arr,mid,H)) {
                //可以吃完 -吃慢一点
                right = mid-1;
                result = Math.min(mid,result);
                count++;
                System.out.println("第"+count+"次,K为："+ mid);

            } else {
                //吃不完 -吃快一点
                left=mid+1;
            }

        }
        System.out.println(result);
    }

    public static boolean canEatAll(int[] arr,int H,int K) {
        int useHours =0;
        for(int i=0;i<arr.length;i++) {
            //todo 巧妙的获得每颗树吃桃要消耗的时间
/*            数学原理
            在 Java 里，两个整数相除的结果会向下取整。比如 5 / 2 的结果是 2 而非 2.5。当我们要计算吃完 peach 个蟠桃，速度为 K 时所需的小时数，直接用 peach / K 计算会有问题，因为它会忽略掉剩余不足 K 个蟠桃时仍需 1 小时吃完的情况。
            我们可以把这个问题转化为求 peach 除以 K 的向上取整结果。设 peach 除以 K 的商是 q，余数是 r，即 peach = q * K + r，其中 0 <= r < K。
            若 r = 0，那么吃完这棵树的蟠桃需要 q 小时。
            若 r > 0，说明在 q 小时后还剩下 r 个蟠桃，还需要额外 1 小时来吃完，所以总共需要 q + 1 小时。
            而 (peach + K - 1) / K 这个表达式就能巧妙地实现向上取整的效果。下面分情况讨论：
            当 peach 能被 K 整除时：设 peach = m * K（m 为整数），那么 (peach + K - 1) / K = (m * K + K - 1) / K。因为 m * K + K - 1 除以 K 的商是 m，余数是 K - 1，整数相除向下取整后结果就是 m，这和 peach / K 的结果一致。
            当 peach 不能被 K 整除时：设 peach = m * K + r（0 < r < K），那么 (peach + K - 1) / K = (m * K + r + K - 1) / K。由于 r + K - 1 肯定大于等于 K，所以 (m * K + r + K - 1) / K 的商是 m + 1，也就是在 m 小时的基础上多了 1 小时，符合我们的需求。*/
            useHours +=(arr[i]+K-1)/K;
        }
        return useHours <=H;
    }
    //方法2回溯法
    // 记录回溯次数，优化回溯算法
    static int num = 0;
    // 吃完所有桃子的最小速度
    static int minSpeed = 0;
    /**
     * 从速度1开始回溯，寻找H小时内吃完所有桃子的最小速度
     */
    private static void dfs(int[] arr, int H, int K) {
        int times = 0;
        for (int i = 0; i < arr.length; i++) {
            num++;
            // 以速度K吃完每颗桃树的时间
            times += arr[i] / K;
            if (arr[i] % K != 0) {
                times++;
            }
        }

        // 因为速度从小到大递增，当时间 <= H时，即最小速度
        if (times <= H) {
            minSpeed = K;
            return;
        } else {
            // 吃不完，加快速度
            dfs(arr, H, ++K);
        }
    }
}
